/*
    created: 2023/5/1
    filename: Hash.h
    author: 李东霖
    purpose：Hash的实现
    这里采用动态分配的方法来控制表长    

*/

#include"Hash.h"

//初始化哈希表  
//参数：初始化表长
//返回值：hash表的表头结点
HashTable* InitHashtable(const _uint32 tablesize)
{
    HashTable* hash = (HashTable*)malloc(sizeof(HashTable));
    if(NULL == hash) return NULL;
    hash->count = 0;
    hash->tablesize = tablesize;

    //申请tablesize个Node
    Node* nodearray = (Node*)malloc((hash->tablesize)*sizeof(Node));
    if(NULL == nodearray) return NULL;
    //保证他的每一个字段都是0
    memset(nodearray,0,(hash->tablesize)*sizeof(Node));
    hash->head = nodearray;

    return hash;
}

//哈希函数  这里就采用取余运算
//参数1：初始化过的哈希表  
//参数2：关键字  
//返回值：该关键字映射的哈希地址  
const _uint32 Hash(HashTable *hash,_uint32 key)
{
    return key%hash->tablesize;  
}

//查找  根据关键字来查找元素  
//参数1：初始化过的哈希表  
//参数2：关键字  
//返回值：该关键字对应的元素结点指针 
Node* Lookup(HashTable *hash,_uint32 key)
{
    const _uint32 index = Hash(hash,key);
    //拿到同义词表头
    Node *head = hash->head[index].next;

    while(head != NULL && head->elem.key != key)
    {
        head = head->next;
    }
    return head;
}

//删除  删除关键字指定的元素  
//参数1：初始化过的哈希表  
//参数2：关键字  
//返回值：-1：哈希表没有初始化 0-成功 1-失败   
int DeleteNode(HashTable *hash,_uint32 key)
{
    const _uint32 index = Hash(hash,key);
    //拿到同义词表头前驱
    Node *head = &hash->head[index];

    while(head->next != NULL && head->next->elem.key != key)
    {
        head = head->next;
    } 
    if(head->next == NULL) return 1;

    Node *del = head->next;
    head->next = head->next->next;
    free(del);
    --(hash->count);
    return 0;
}

//插入  根据关键字插入元素  
//参数1：初始化过的哈希表  
//参数2：关键字  
//返回值：-1：哈希表没有初始化 0-成功 1-失败  
int Insert(HashTable *hash,Element* elem)
{
    //关键字是否已经存在
    if(NULL != Lookup(hash,elem->key))
    {
        printf("elem exist\n");
        return 1;
    } 

    //为了保证效率，我们采取头插法  
    const _uint32 index = Hash(hash,elem->key);
    //拿到同义词表头前驱
    Node *head = &(hash->head[index]);
    Node* ins = (Node*)malloc(sizeof(Node));
    memcpy(&ins->elem,elem,sizeof(Element));
    ins->next = head->next;
    head->next = ins;
    ++(hash->count);
    return 0;
}

//销毁哈希表
//参数1：初始化过的哈希表    
void DistroyHash(HashTable **hash)
{
    if(*hash == NULL) return;
    Node* p;
    Node* del;
    for(size_t i = 0; i != (*hash)->tablesize; ++i)
    {
        p = (*hash)->head[i].next;
        while(p != NULL)
        {
            del = p;
            p = p->next;
            free(del);
        }
    }
    free((*hash)->head);
    free(*hash);
    *hash = NULL;
}

//打印哈希表  
//打印的格式  同一哈希地址下的所有同义词  
//参数1：初始化过的哈希表  
void Display(HashTable* hash)
{
    for (size_t i = 0; i != hash->tablesize; ++i)
    {
        Node *p = hash->head[i].next;
        while(p != NULL)
        {
            printf("%d-%d\n",p->elem.key,p->elem.val);
            p = p->next;
        }
        printf("\n");
    }
}